package com.yehui.algorithm.sword;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;

/**
 * 输入一个字符串,按字典序打印出该字符串中字符的所有排列。
 * 例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
 * 结果请按字母顺序输出。
 * Created by XuChunH on 2016/9/16.
 */
public class Permutation {

    public ArrayList<String> Permutation(String str) {
        ArrayList<String> result = new ArrayList<>();
        if(str == null || str.length() == 0){
            return result;
        }
        HashSet<String> hashSet = new HashSet<>();
        permutation(hashSet, str.toCharArray(), 0);
        result.addAll(hashSet);
        Collections.sort(result);
        return result;
    }

    private void permutation(HashSet<String> hashSet, char[] str, int k) {
        if (k == str.length) {
            hashSet.add(new String(str));
            return;
        }
        for (int i = k; i < str.length; i++) {
            swap(str, i, k);
            permutation(hashSet, str, k + 1);
            swap(str, i, k);
        }
    }

    private void swap(char[] str, int i, int j) {
        if (i != j) {
            char t = str[i];
            str[i] = str[j];
            str[j] = t;
        }
    }
}
